package BinaryTree;


import java.util.*;

public class BinaryTree {

    // 根节点
    public BinaryNode root;

    static class BinaryNode{
        public String val;
        public BinaryNode left;
        public BinaryNode right;

        public BinaryNode(String val) {
            this.val = val;
        }

    }
    // 先手动实现二叉树
    public BinaryNode create(){
        BinaryNode A=new BinaryNode("A");
        BinaryNode B=new BinaryNode("B");
        BinaryNode C=new BinaryNode("C");
        BinaryNode D=new BinaryNode("D");
        BinaryNode E=new BinaryNode("E");
        BinaryNode F=new BinaryNode("F");
        BinaryNode G=new BinaryNode("G");
        BinaryNode H=new BinaryNode("H");

        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        D.left=H;

        root=A;
        return root;
    }
    public BinaryNode create2(){
        BinaryNode E=new BinaryNode("E");
        BinaryNode F=new BinaryNode("F");
        BinaryNode G=new BinaryNode("G");
        BinaryNode H=new BinaryNode("H");


        E.left=F;
        F.left=G;
        G.right=H;

        root=E;
        return root;
    }
    public BinaryNode create3(){
        BinaryNode A=new BinaryNode("A");
        BinaryNode B=new BinaryNode("B");
        BinaryNode C=new BinaryNode("C");
        BinaryNode D=new BinaryNode("D");
        BinaryNode E=new BinaryNode("E");
        BinaryNode F=new BinaryNode("F");
        BinaryNode G=new BinaryNode("G");

/*
        A.left=B;
        A.right=C;
        B.left=D;
        C.right=E;
        D.left=F;
        E.right=G;*/
        A.right=B;
        B.right=C;
        C.right=D;
        D.right=E;
        E.right=F;

        root=A;
        return root;
    }

    // 前序遍历: 根 左 右
    void preOrder(BinaryNode root){
        if(root == null){
            return ;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    // 非递归前序遍历: 一
    public List<String> preorderTraversal(BinaryNode root) {
        List<String> s=new LinkedList<>();
        if(root == null){
            return s;
        }
        s.add(root.val);
        List<String> retleft=preorderTraversal(root.left);
        s.addAll(retleft);
        List<String> retright=preorderTraversal(root.right);
        s.addAll(retright);
        return s;

    }
    // 二
    public void preorderNor(BinaryNode root){
        if(root == null){
            return ;
        }
        Stack<BinaryNode> stack=new Stack<>();
        BinaryNode cur=root;
        while(cur!=null || !stack.isEmpty()) {

            while (cur != null) {
                System.out.print(cur.val + " ");
                stack.push(cur);
                cur = cur.left;
            }
            BinaryNode top = stack.pop();
            cur = top.right;
        }
    }

    // 中序遍历
    void inOrder(BinaryNode root){
        if(root == null){
            return ;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    // 非递归中序遍历
    public List<String> inorderTraversal(BinaryNode root) {
        List<String> s=new LinkedList<>();
        if(root == null){
            return s;
        }

        List<String> retleft=inorderTraversal(root.left);
        s.addAll(retleft);
        s.add(root.val);
        List<String> retright=inorderTraversal(root.right);
        s.addAll(retright);
        return s;

    }
    // 二
    public void inorderNor(BinaryNode root){
        if(root == null){
            return ;
        }
        Stack<BinaryNode> stack=new Stack<>();
        BinaryNode cur=root;
        while(cur!=null || !stack.isEmpty()) {

            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            BinaryNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }
    // 后序遍历
    void postOrder(BinaryNode root){
        if(root == null){
            return ;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    // 非递归后序遍历
    public List<String> postorderTraversal(BinaryNode root) {
        List<String> s=new LinkedList<>();
        if(root == null){
            return s;
        }

        List<String> retleft=postorderTraversal(root.left);
        s.addAll(retleft);
        List<String> retright=postorderTraversal(root.right);
        s.addAll(retright);
        s.add(root.val);
        return s;
    }
    // 二
    public void postorderNor(BinaryNode root){
        if(root == null){
            return ;
        }
        Stack<BinaryNode> stack=new Stack<>();
        BinaryNode cur=root;
        BinaryNode prev=null;
        while(cur!=null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            BinaryNode top = stack.peek();

            if(top.right == null || top.right == prev) {
                System.out.print(top.val+" ");
                stack.pop();
                prev = top;
            }else {
                cur = top.right;
            }
        }
    }




    // 获取树中节点的个数
    int size(BinaryNode root){
        // 根节点为空
        if(root == null ){
            return 0;
        }
        // 不为空，加上左子树和右子树节点个数
        return size(root.left)+size(root.right)+1;
    }
    // 获取叶子节点的个数
    int getLeafNodeCount(BinaryNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+
                getLeafNodeCount(root.right);
    }

    // 子问题思路-求叶子结点个数
    // 获取第K层节点的个数
    int getKLevelNodeCount(BinaryNode root,int k){
        if(root == null ){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+
                getKLevelNodeCount(root.right,k-1);

    }
    // 获取二叉树的高度
    int getHeight(BinaryNode root){
        if(root == null){
            return 0;
        }
        // 算出左子树的最大高度
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
    }
    // 检测值为value的元素是否存在
    BinaryNode find(BinaryNode root, String val){
        if(root ==null ){
            return null;
        }
        if(root.val==val){
            return root;
        }
        BinaryNode left=find(root.left,val);
        if(left != null){
            return left;
        }
        BinaryNode right=find(root.right,val);
        if(right != null){
            return right;
        }
        return null;
    }

    @Override
    public String toString() {
        return "BinaryTree{" +
                "root=" + root.val +
                '}';
    }

    // 判断两个树是否相等
    public boolean isSameTree(BinaryNode p, BinaryNode q) {
        // 首先判断是否为空
        if(p == null&& q!=null || p!=null && q==null){
            return false;
        }
        if(p == null && q==null){
            return true;
        }
        if(p.val!=q.val){
            return false;
        }
        // 这里p 和 q 都不为空,并且p和q的根节点都相等
        // 当p q的左右子树都相同时，在返回true
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    // 查看两树是否为子树关系
    public boolean isSubtree(BinaryNode root, BinaryNode subRoot) {
        if(root==null){
            return false;
        }
        //  先看两树是否相等
        if(isSameTree(root,subRoot)){
            return true;
        }
        // 再看是否是 子树关系
        if(isSubtree(root.left,subRoot) ){
            return true;
        }
        if(isSubtree(root.right,subRoot)) {
            return true;
        }

        return false;
    }

    // 二叉树反转
    public BinaryNode invertTree(BinaryNode root) {
        if(root==null){
            return null;
        }
        // 叶子节点, 就返回该根节点
        if(root.left == null && root.right==null){
            return root;
        }

        // 进行交换
        BinaryNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;

        //  再将左右子树进行反转
        BinaryNode a=invertTree(root.left);
        BinaryNode b=invertTree(root.right);

        return root;
    }

    //判断平衡二叉树
    /* 法一： 求每个子树的深度，保证每个子树都是 平衡二叉树
       但是时间复杂度就达到了 O(N^2) ----相当于每次遍历某个节点都要算深度
    public boolean isBalanced(BinaryNode root) {
        // 判断是否为空
        if(root == null){
            return true;
        }
        int leftHeight=getHeight2(root.left);
        int rightHeight=getHeight2(root.right);
        // 平衡二叉树的根节点的左右节点的子树的深度相差不超过1
        return Math.abs(leftHeight-rightHeight)<=1 && isBalanced(root.left) && isBalanced(root.right);
    }
    public int getHeight2(BinaryNode root){
        if(root == null){
            return 0;
        }
        // 算出左右子树的最大高度
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
    }*/

    // 法二： 边判定是否为平衡二叉树，边算深度
    public boolean isBalanced(BinaryNode root) {
        // 判断是否为空
        if(root == null){
            return true;
        }
        // 判断是否为 平衡二叉树
        return getHeight(root)>=0;
    }
    public int getHeight2(BinaryNode root){
        if(root == null){
            return 0;
        }
        // 算出左右子树的最大高度
        int leftHeight=getHeight2(root.left);
        //  如果左右子树的高度绝对值差大于1 ，说明子树不是平衡二叉树，那就返回-1；直接退出
        if(leftHeight == -1){
            return -1;
        }
        int rightHeight=getHeight2(root.right);
        // 如果深度满足平衡二叉树的要求, 再看是否满足 子树均满足二叉树
        if(Math.abs(leftHeight-rightHeight)<=1 && leftHeight >=0 && rightHeight>=0){
            return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
        }else{
            return -1;
        }

    }


    // 判断二叉树是否轴对称
    public boolean isSymmetric(BinaryNode root) {
        if(root == null){
            return false;
        }
        if(isSymmetrichild(root.left,root.right)){
            return true;
        }
        return false;
    }

    public boolean isSymmetrichild(BinaryNode p,BinaryNode q){
        if(p == null&& q!=null || p!=null && q==null){
            return false;
        }
        if(p==null && q==null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        // 到这里 ，p q 不为空且val值相等
        return isSymmetrichild(p.left,q.right) &&
                isSymmetrichild(p.right,q.left);
    }





    // 根据给出的一串字符构建二叉树
    // 创建树
    class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val){
            this.val=val;
        }
    }
    static int i=0;
    public  TreeNode creatTree(String s){

        if(s.isEmpty()){
            return null;
        }
        char a=s.charAt(i);
        i++;
        // 如果 a 是 #
        if(a == '#'){
            return null;
        }
        TreeNode root=new TreeNode(a);
        root.left=creatTree(s);
        root.right=creatTree(s);
        return root;
    }
    // 实现中序遍历
    public  void inorder(TreeNode root){
        if(root == null){
            return ;
        }
        inorder(root.left);

        System.out.print(root.val+" ");

        inorder(root.right);
    }





    //层序遍历
   public void levelOrder(BinaryNode root) {
       // 判空
       if (root == null) {
           return;
       }
       // 定义一个队列，用来存储每层数据
       Queue<BinaryNode> queue = new LinkedList();
       queue.add(root);
       while (!queue.isEmpty()) {
           // 用来记录输出的值，再看输出的节点是否含有左右节点
           BinaryNode cur=queue.poll();
           System.out.print(cur.val+" ");

           if (cur.left != null) {
               // 当左节点不为空时， 将左节点压入队列
               queue.add(cur.left);
           }
           if (cur.right != null) {
               queue.add(cur.right);
           }
       }
   }


    public List<List<String>> levelOrder2(BinaryNode root) {
        List<List<String>> list=new ArrayList<>();

        // 判空
        if (root == null) {
            return list;
        }
        // 定义一个队列，用来存储每层数据
        Queue<BinaryNode> queue = new LinkedList();
        queue.add(root);

        while (!queue.isEmpty()) {
            // 记录队列中的个数，实际为每一层的节点数
            int size= queue.size();
            // 用来存储每一层数据
            List<String> list2=new ArrayList<>();

            while(size!=0){
                BinaryNode cur=queue.poll();
                list2.add(cur.val);
                size--;
                if (cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }

            list.add(list2);
        }
        return list;
    }


     // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(BinaryNode root){
        if(root == null){
            return false;
        }
        Queue<BinaryNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            // 定义一个节点记录 队列输出值
            BinaryNode cur=queue.poll();
            if(cur==null){
                break;
            }
            queue.add(cur.left);
            queue.add(cur.right);
        }
        //到这里 队列中出现了null ，如果剩余队列中全为null 则为完全二叉树
        while(!queue.isEmpty()){
            BinaryNode cur=queue.poll();
            if(cur==null){

            }else{
                return false;
            }
        }
        return true;
    }




/*    // 求二叉树中某2个节点的就近祖先
        //  法一：
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(root == p||root ==q){
            return root;
        }
        TreeNode leftNode=lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode=lowestCommonAncestor(root.right,p,q);

        // 如果左右都有
        if(leftNode != null && rightNode != null){
            return root;
        }else if(leftNode !=null){
            return leftNode;
        }else{
            return rightNode;
        }
    } */

    // 法二： 通过找出他们的遍历路径， 将其存入栈中，在来核对
      public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {

          if(root == null) return null;

          Stack<TreeNode> stackP = new Stack<>();
          Stack<TreeNode> stackQ = new Stack<>();

          getPath(root,p,stackP);
          getPath(root,q,stackQ);

          int sizeP = stackP.size();
          int sizeQ = stackQ.size();

          if(sizeP > sizeQ) {
               int size = sizeP - sizeQ;
               while(size != 0) {
                  stackP.pop();
                   size--;
               }
    }else {
        int size = sizeQ - sizeP;
        while(size != 0) {
            stackQ.pop();
            size--;
        }
    }
    //两个栈当中的元素是一样多
    while(!stackP.isEmpty() && !stackQ.isEmpty()) {
        if(stackP.peek() == stackQ.peek()) {
            return stackP.peek();
        }else{
            stackP.pop();
            stackQ.pop();
        }
    }

    return null;
}

    private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack) {
        if(root == null || node == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean flg = getPath(root.left,node,stack);
        if(flg) {
            return true;
        }
        boolean flg2 = getPath(root.right,node,stack);
        if(flg2) {
            return true;
        }

        stack.pop();

        return false;
    }



    public class TreeNode2 {
      int val;
      TreeNode2 left;
     TreeNode2 right;
    TreeNode2() {}
     TreeNode2(int val) { this.val = val; }
     TreeNode2(int val, TreeNode2 left, TreeNode2 right) {
         this.val = val;
        this.left = left;
         this.right = right;
    }
 }

    public  static int index;
    public TreeNode2 buildTree(int[] preorder, int[] inorder) {
        TreeNode2 root = buildTreeChild(preorder,inorder,0,inorder.length-1);
        return root;
    }
    public TreeNode2 buildTreeChild (int[] preorder, int[] inorder,int ibegin,int iend) {
        if(ibegin>iend){
            return null;
        }
        // 先实例化 根节点
        if(index>=preorder.length){
            return null;
        }
        TreeNode2 root=new TreeNode2(preorder[index]);
        // 找到根节点
        int n=findIndex(inorder,ibegin,iend,preorder[index]);
        if(n == -1){
            return null;
        }
        index++;
        root.left=buildTreeChild (preorder,inorder,ibegin,n-1);
        root.right=buildTreeChild (preorder,inorder,n+1,iend);

        return root;
    }

    // 从中序遍历 中 找到 前序遍历中 的节点
    public int findIndex(int[] inorder,int ibegin,int iend,int key){
        for(int i=ibegin;i<=iend;i++){
            if(inorder[i] == key){
                return i;
            }
        }
        // 没找到
        return -1;
    }




}
